// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
public class Code03_CopyListWithRandomPointer {
    // 不要提交这个类，这是内部辅助类，用于表示链表节点
    public static class Node {
        public int val;
        public Node next;
        public Node random;

        // 构造函数，用于创建一个新节点并初始化其值
        public Node(int v) {
            val = v;
        }
    }

    // 提交如下的方法，用于复制带随机指针的链表
    public static Node copyRandomList(Node head) {
        // 如果原链表头节点为null，直接返回null，因为空链表的副本也是空链表
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // 1 -> 2 -> 3 ->...
        // 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' ->...
        // 这个循环的目的是在原链表的每个节点后面插入一个复制节点
        while (cur!= null) {
            // 保存当前节点cur的下一个节点
            next = cur.next;
            // 创建一个新节点，其值与当前节点cur相同，并将其插入到cur后面
            cur.next = new Node(cur.val);
            // 将新节点的下一个节点设置为之前保存的next节点
            cur.next.next = next;
            // 将cur移动到下一个原节点（即之前保存的next节点）
            cur = next;
        }
        cur = head;
        Node copy = null;
        // 利用上面新老节点的结构关系，设置每一个新节点的random指针
        while (cur!= null) {
            // 保存当前节点cur的下一个节点的下一个节点（即下一个原节点的下一个节点）
            next = cur.next.next;
            // 获取当前原节点cur后面的复制节点
            copy = cur.next;
            // 如果当前原节点cur的random指针不为null，
            // 则复制节点copy的random指针应该指向原节点cur的random指针指向的节点的下一个节点（即对应的复制节点）
            // 如果cur.random为null，则copy.random也为null
            copy.random = cur.random!= null? cur.random.next : null;
            // 将cur移动到下一个原节点
            cur = next;
        }
        Node ans = head.next;
        cur = head;
        // 新老链表分离 : 老链表重新连在一起，新链表重新连在一起
        while (cur!= null) {
            // 保存当前节点cur的下一个节点的下一个节点（即下一个原节点的下一个节点）
            next = cur.next.next;
            // 获取当前原节点cur后面的复制节点
            copy = cur.next;
            // 将原链表中当前节点cur的下一个节点重新连接为下一个原节点（即恢复原链表结构）
            cur.next = next;
            // 将复制链表中当前复制节点copy的下一个节点连接为下一个原节点的下一个节点（如果next不为null）
            copy.next = next!= null? next.next : null;
            // 将cur移动到下一个原节点
            cur = next;
        }
        // 返回新链表的头节点，新链表是原链表的副本，包含了相同的值和正确的random指针关系
        return ans;
    }
}